//1.动态规划
class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m, vector<int>(n,1));
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                dp[i][j] =  dp[i-1][j] +  dp[i][j-1]; // 等价于 dp[i][j] = dp[i-1][j] + dp[i][j-1]
            }
        }
        return dp[m-1][n-1];
    }
};

//2.状态压缩优化版本(空间复杂度降低)---晕
class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<int> f(n,1);
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                f[j]+=f[j-1];
            }
        }
        return f[n - 1];
    }
};

